COMMENT ⊗   VALID 00006 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00013 00003	Proposed Research
C00018 00004
C00023 00005	Mathematical problems of non-monotonic reasoning
C00026 00006	Additional references beyond those listed in the accomplishments section.
C00029 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.cb Proposal for Basic Research in Artificial Intelligence
.<<nsf.84[w84,jmc]		1984 NSF proposal for Basic Research in AI>>

	This is an accomplishment-based renewal proposal.

	Four papers, one report, one joint paper accepted for
publication and one paper submitted for
publication are the published basis for this renewal.

The papers are:

%3McCarthy, John (1979)%1:
"Ascribing Mental Qualities to Machines" in %2Philosophical Perspectives 
in Artificial Intelligence%1, Ringle, Martin (ed.), Harvester Press, July 1979.
.<<aim 326, MENTAL[F76,JMC]>>

Computer programs vary much more than people in the extent and nature
of the intentional properties that may be usefully ascribed to them.
This paper outlines criteria for ascribing specific mental qualities,
e.g specific beliefs and goals, to computer programs and machines in
general.  A popular version appeared in %2Psychology Today%1, December
1983.  John Perry expressed interest in including one or the other
in his forthcoming %2Oxford Readings in Philosophy%1 volume.

%3McCarthy, John (1979)%1: 
"First Order Theories of Individual Concepts and Propositions", 
in Michie, Donald (ed.) %2Machine Intelligence 9%1, (University of
Edinburgh Press, Edinburgh).
.<<aim 325,concep[e76,jmc]>>

This paper presents a variety of formalisms for expressing facts
about knowledge and belief.  What was new was sticking to first
order logic but keeping the objects of belief, etc. as abstract
objects rather than making them sentences.  With the aid of
notions of standard concepts certain puzzling sentences discussed
in the philosophical literature can be neatly expressed in a form
that permits derivation of their consequences.  However, the
motivation for the work is AI not philosophy.

%3McCarthy, John (1980)%1: 
"Circumscription - A Form of Non-Monotonic Reasoning", %2Artificial
Intelligence%1, Volume 13, Numbers 1,2, April.
.<<aim 334, circum.new[s79,jmc]>>

This is the most important of the six papers and reports and the
one that has received the most attention from other scientists.
The need for non-monotonic reasoning in AI and in database theory
became apparent in the middle 70s and several systems were proposed.
The issue of %2Artificial Intelligence%1 in which this paper appeared
contains two other proposals.  I believe that circumscription is
the most successful of them.  Further papers on circumscription were
written by Raymond Reiter of the University of British Columbia,
Jack Minker of the University of Maryland and Vladimir Lifschitz of
the University of Texas at El Paso.  I have a new paper on circumscription,
but there is one problem I would like to solve before publishing it.

%3McCarthy, John (1982)%1: "Common Business Communication Language", in
%2Textverarbeitung und B%B:%*urosysteme%1, Albert Endres and J%B:%*urgen Reetz, eds.
R. Oldenbourg Verlag, Munich and Vienna 1982.

Since much office work consists in communicating with other organizations,
increasing office productivity requires that computers belonging to different
organizations communicate with one another about business matters.
The paradigm case involves a cost analysis program getting bids for
components from the computers belonging to potential suppliers.  The
idea started as a simple proposal for standardization, but it turned
up important unsolved problems in the semantics and pragmatics of
natural language.  Indeed it led to the conclusion that putting
natural language front ends on existing programs is the wrong problem.
The point isn't to express in natural language what we already express
in some kind of computerese, but to express formally concepts, facts
and requests that have heretofore only been expressable in natural
language.

%3Gabriel, Richard P. and John McCarthy (1984)%1: "Queue-based
Multi-processing Lisp", accepted for publication in the proceedings
of the 1984 Lisp Conference to be held in Austin in August.

Getting greater performance from computers requires parallelism,
and LISP has traditionally been regarded as a somewhat recalcitrant
language from this point of view.  The paper contains
a few constructs to be added to LISP to make efficient use of
parallel processors.  The original versions of the ideas are mine,
but their subsequent development and all the implementation work
are my co-author's.

%3McCarthy, John (1982)%1: %2Coloring Maps and the Kowalski Doctrine%1,
Report No. STAN-CS-82-903, Computer Science Department, Stanford University,
Stanford, CA 94305.

Robert Kowalski, who, along with Alain Colmerauer, originated logic
programming, expressed the doctrine "Algorithm equals logic plus
control".  Several authors (including Keith Clark, Luis Pereira and
Herv%B`%*e Gallaire),
most prominently in connection with
logic programming, have proposed formalisms in which logic and
control can be expressed separately.  The advantage is this.  The
logic of an algorithm can often be expressed in a simple way that
is easy to understand and in terms of which, the algorithm can
be proved to give the desired results.  However, efficient execution
often requires complicated control.  It seemed to me that the
control schemes that have been proposed are very limited, and
that the problem of coloring maps presents some interesting
problems of separating logic and control.  Both the postponement
control and the Kempe control discussed in the article have more
general applications.  After the referenced report was written,
further work done during a visit to Kowalski at Imperial College
resulted in a notion of "introspective programming" in which
a Prolog program can look at its own goal and search trees.
A small "introspective Prolog interpreter" was implemented by
Peter Szeredi of the Hungarian Academy of Sciences, and publication
of the paper awaits incorporation of the idea of introspection
and reference to Szeredi's (unpublished) work.

%3McCarthy, John (1984)%1:
"Applications of Circumscription to Formalizing Common Sense Knowledge".
This is has been submitted to the 1984 AAAI
conference on non-monotonic reasoning, which will not have a proceedings
and is being submitted for publication to %2Artificial Intelligence%1.

Abstract: We present a new and more symmetric version of the
circumscription method of non-monotonic reasoning (McCarthy 1980) and some
applications to formalizing common sense knowledge.  The applications in
this paper are based on minimizing the abnormality of the different
aspects of a situation.  Included are non-monotonic treatments of ⊗is-a 
hierarchies, the unique names hypothesis, and the frame problem.

I mistakenly delayed submitting this proposal until this paper was
completed.  Naturally it took longer than expected.  However, it contains
the current state of applying circumscription to formalizing common
sense knowledge and reasoning.
.skip 2
Proposed Research

	As the submitted papers show, I have been active in a variety
of fields of computer science and will continue to work on ideas
that occur to me.

	However, the main long term goal of my research has always been to
find ways of formalizing common sense knowledge and reasoning ability so
that a computer program can have the common sense knowledge and the common
sense ability to achieve the goals we give it.

	We distinguish common sense knowledge and common sense ability.
Common sense knowledge includes facts about how events occur in time,
about the effects of actions by the knower and others, facts about the
relation between phenomena in the world and what a person or program with
sensory capabilities can learn about it, facts about physical objects and
how they are perceived, and about their properties and their relations to
one another.  An example is the fact that eggs contain a yolk and a white
and a shell, how to recognize an egg, the effects of hard boiling them and
the effects of dropping them.  Common sense ability involves the use of
common sense knowledge and the observation of the world to decide what to
do to achieve one's goals.  The "common" in "common sense" refers to the
fact that a large amount of this knowledge and ability is common to all
humans.  Not much of it is understood well enough to include it in
computer programs.

	Expressing common sense knowledge in languages of mathematical
logic and using controlled deduction as a way of deciding what to
do was first proposed in (McCarthy 1960).  This proved very difficult
and progress was slow.  Many people gave up on using logic in AI
and proposed other formalisms, but in the main they proved to be
equivalent to subsets of logical languages, and much attention in
AI has returned to logic.

	A major advance in the use of logical languages for AI was
the notion of formalized non-monotonic reasoning which arose in
the middle 1970s.  My proposal was called circumscription
(McCarthy 1980).  A preliminary version under the name %2minimal
inference%1 was included in (McCarthy 1977).

	The idea of non-monotonic reasoning and the circumscription
approach to formalizing it seem to have wider applicability than
was previously envisioned.  We plan to continue our previous
investigations of formalizing common sense knowledge using circumscription
as a tool.  However, there seem to be many new applications in AI
but also in databases, programming languages and even in analytic
philosophy.  Our chief objective in the next three
years will be to explore these new possibilities.  Here are some of them.


Formalization of common sense

	For a long time, the lack of formalized non-monotonic
reasoning has impeded the formal expression of
common sense knowledge and writing programs that carry out common
sense reasoning.  This situation has been somewhat relieved by
the advent of circumscription and other non-monotonic reasoning
systems.  In particular the circumscription formulation of the
frame problem of (McCarthy 1984) seems to me to be satisfactory.

	Therefore, it seems to be time to extend the formalization
of common sense knowledge to some new domains.  I have the following
in mind, but the subject is now exciting increased interest among
graduate students, so it may be possible to do more.

	1. The blocks world with incomplete expression of the results
of action.  All formalizations of the blocks world that I know about,
including those in the literature on planning, use complete rules.
Namely, the result of an action is fully described.  However, common
sense knowledge of the effects of action is often incomplete in
many respects.  For example, we know that when block A is placed
on block B, A will be on B in the resulting situation, but neither our
verbal expression of such rules nor our informal knowledge formulates
where on B, block A will be.  Rather than devise a language for
expressing the precise location of one block on another we need
to formalize the common sense knowledge about this that people
and robots with similar opportunities to observe can actually have.

	2. A problem in which a person achieves a goal by asking
another person for help, knowing that the other person is willing
and can help in the manner desired.  This example admits many
non-monotonic shortcuts, which are often important in practice.
For example, it can be taken as standard that a person knows
what he can do.  The contrary is an abnormality.  We propose
to formalize the common sense knowledge of how to achieve
goals that require the co-operation of other agents.

	3. Perhaps the most obvious almost untouched problem for
formalization of common sense knowledge concerns concurrent processes.
The formalizations of concurrent processes used in studying parallel
computation are mostly irrelevant, because they concern processes
which the theorist has the privilege of designing.  The designs
make much of the problem of synchronization, but this is little
considered in common sense reasoning.  Thus when contemplating
walking down a corridor a person doesn't plan in advance how
he and a person going the other way are to avoid permanently
blocking each other.

	4. We propose to continue our previous work in formalizing
knowledge about people's knowledge.  Some of it is in
(McCarthy, Sato, Igarashi and Hayashi 1977), but most of it,
some quite old, is still unpublished.  Recently Ron Fagin,
Joe Halpern, Moshe Vardi of IBM San Jose and Yoram Moses of
my group have begun new work in the subject that makes
further pursuit of my old ideas more promising.

.skip 1
Mathematical problems of non-monotonic reasoning

	Circumscription presents many problems of a mathematical
logical nature whose solution will be important for applications.
Here are some on which I propose to work.  An invited address to
a meeting of the Association for Symbolic Logic in January 1985
will provide an opportunity to present a few results but mostly
to attract the attention of professional mathematical logicians
to this important new domain.

	1. When is the second order formula of circumscription
equivalent to a first order formula?  This is true of all but
one of the examples of (McCarthy 1980), and some general partial
results have been obtained by me and by Vladimir Lifschitz of
the University of Texas at El Paso.

	2. Can Reiter's (1980) "unique names hypothesis" be expressed
non-monotonically by a second order formula?  It can be done
with circumscription provided that names are the only objects
in the theory, but this seems undesirable.  There seems to be
a relation between this problem and the notion of a figure being
in general position.

	3. In many cases circumscription formulas "compile" rather
directly into executable Prolog programs.  It is important to know 
when this is the case and when the implementation of circumscription
requires different mechanisms.

	4. In what cases is the question of whether a sentence
is implied by the circumscription of a set of sentences decidable?
It is true in the propositional case and when all the predicates
are monadic.  This suggests exploring analogs of the decidable cases
of the first order logic decision problem.  However, the propositional
case already corresponds to a tree of propositional satisfaction
problems, so circumscriptive inferability is likely to be harder
than ordinary deducibility.
Additional references beyond those listed in the accomplishments section.

%3Lifschitz, Vladimir%1(1983): unpublished note on circumscription

%3McCarthy, John (1977)%1:
"Epistemological Problems of Artificial Intelligence", %2Proceedings
of the Fifth International Joint Conference on Artificial 
Intelligence%1, M.I.T., Cambridge, Mass.
ijcai.c[e77,jmc]

%3Reiter, Raymond (19xx)%1: (concerning unique names)

%3Reiter, Raymond (1982)%1: "Circumscription Implies Predicate Completion
(Sometimes)", Proceedings of the National Conference on Artificial
Intelligence, AAAI-82.